Реклама

Tproger всё о программировании

Написать пост

Войти

Что вы читаете, смотрите и покупаете, чтобы нам быть в теме — поделитесь опытом

Лента

Лента

Новости

Новости

Флудильня

Флудильня

Карта дня

Карта дня

Викторины

Викторины

Компании

Компании

Курсы

Курсы

События

События

Языки

Языки

Python

JavaScript

C++

Java

PHP

CSS

C#

Ещё...

Темы

Темы

Веб-разработка

Алгоритмы

Разработка игр

Искусственный интеллект

Нейронные сети

Мобильная разработка

Паттерны проектирования

Машинное обучение

Data Science

Тестирование

Ещё...

Заказать рекламу

О нас

Мы в Telegram

Другие соц. сети

Правила

Ещё

Рассказать о баге

Информация

О битовых операциях

Типичный программист
10 мар 2016 Отредактировано 21 февр 2024

25

157К открытий164К показов

В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

|  (Побитовое ИЛИ (OR)),

& (Побитовое И (AND)),

^ (Исключающее ИЛИ (XOR)),

~ (Побитовое отрицание (NOT)),

<< (Побитовый сдвиг влево),

>> (Побитовый сдвиг вправо).

Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

О битовых операторах вам также необходимо знать:

Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.

Большинство битовых операций являются операциями составного присваивания.

Побитовое ИЛИ (OR)

Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:

38 | 53 будет таким:

В итоге мы получаем 1101112 , или 5510 .

Побитовое И (AND)

Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

Как результат, получаем 1001002 , или 3610 .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

… 101000012 , или 16010

С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.

Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

String msg = "This is a message";
char[] message = msg.toCharArray();
String key = ".*)";
String encryptedString = new String();
for(int i = 0; i< message.length; i++){
encryptedString += message[i]^key.toCharArray()[i%key.length()];
}

Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

Побитовое отрицание (NOT)

Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

Вот, например, операция ~52:

Результатом будет 20310

При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.

Дополнительный код

Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

Например, если мы имеем 109:

Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

Побитовый сдвиг влево

Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2N. Таким образом, 43<<4 == 43*Math.pow(2,4). Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Побитовый сдвиг вправо

Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.

Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2N. Опять же, это выполняется намного быстрее обычного деления.

Вывод

Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

Следите за новыми постами по любимым темам

Поразрядная обработкаПодписаться

Красивый хакПодписаться

Лучшая практикаПодписаться

ОптимизацияПодписаться

25

157К открытий164К показов

Также рекомендуем

Как понять партиционирование: DWH для гуманитариев

Вместе с Никитой Егоровым, ведущим аналитиком в МТС Диджитал, объясняем принципы партиционирования простыми аналогиями, сравниваем с шардированием, разбираем стратегии разбиения данных и популярные инструменты (PostgreSQL, BigQuery, ClickHouse).

🔥 Python 3.14 стал быстрее до 30% благодаря новому интерпретатору. В чем магия?

Python 3.14 стал до 30 % быстрее благодаря новому интерпретатору с tail call — ускорение без изменений в коде, просто обновите версию

Секрет сокращения расходов на запуск кластеров Kubernetes от Adidas Platform

Adidas поделилась успешным опытом сокращения затрат на использование Kubernetes-кластеров в AWS до 50%. Ключевые меры включают использование Karpenter, автоматические Vertical Pod Autoscalers (VPA), инструмент kube-downscaler и оптимизацию параметров ресурсов

Защита API-ключей: как избежать утечек

Защита API-ключей. Показываем, как избежать утечек в API. Рассматриваем пошаговую инструкцию и инструменты ✔ Tproger

Реклама

Школа Айти Авторов

В закрытом канале мы учим авторов писать лучше и зарабатывать больше на статьях про технологии

Подписаться на канал

Лучшие статьи недели

Не пропустите самые интересные и популярные статьи!

Подписаться
Нажимая «Подписаться», вы принимаете условия передачи данных и политику конфиденциальности .

Обсуждают сейчас

Анастасия Колесникова

01 авг 202501 авг 2025 в 22:35

&gt;&gt; Используем MSI файл и следуем инструкциям.

Какой файл? где откуда...

&gt;&gt; Проверяем корректность установки, создав и выполнив файл C:\Projects\Go\test.go:

Где создавать, что выполнять, как выполнять..

У меня в папке Go файл в целом невозможно создавать, только на рабочем столе блонкнот там и перемещать .go формата уже.. Но это же кринж какой-то
Golang: основы для начинающих

Дмитрий Козлов

01 авг 202501 авг 2025 в 21:38

Тема создана для опроса?
Основатель YC-стартапа рассказал о самом коротком и странном собеседовании в своей жизни

Сергей Уколов

01 авг 202501 авг 2025 в 16:30

Obsidian если в одно лицо. Если с командой: большая - Yandex Wiki, небольшая - AFFiNE (почти полный аналог Notion в глубокой разработке, наткнулся пару месяцев назад)
Где вести базу знаний по проекту: альтернативы Notion для айтишников в 2025

Евгений Стребков

01 авг 202501 авг 2025 в 13:02

На мой взгляд сегодня это лучшая альтернатива
Где вести базу знаний по проекту: альтернативы Notion для айтишников в 2025

Скопировать токен

О рекламодателе

Реклама на tproger.ru

Мы тоже используем куки, потому что без них вообще ничего не работает

Хорошо

Хорошо

Скопировать токен

О рекламодателе

Реклама на tproger.ru